/**
 * 
 */
package tree.passed2;

import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

import tree.LevelByLevelTraversal;
import tree.Node;

/**
 * @author Michael
 *
 *http://www.leetcode.com/2010/09/saving-binary-search-tree-to-file.html
 */
public class ReconstructBST {

	public static Node<Integer> readBST(List<Integer> preOrder) {
		return readBSTHelper(preOrder, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	
	// O(n)
	public static Node<Integer> readBSTHelper(List<Integer> preOrder, int min, int max) {
		if (preOrder.isEmpty())
			return null;
		
		Node<Integer> node = null;
		int val = preOrder.get(0);
		if (val > min && val < max) {
			preOrder.remove(0);
			node = new Node<Integer>(val);
			node.left = readBSTHelper(preOrder, min, val);
			node.right = readBSTHelper(preOrder, val, max);
		}
		
		return node;
	}
	
	public static Node<Integer> readBSTInsert(List<Integer> preOrder) {
		Node<Integer> root = null;
		for (int i = 0, size = preOrder.size(); i < size; ++i) {
			root = insertBSTIterativeHelper(root, preOrder.get(i));
		}

		return root;
	}
	
//	public static Node<Integer> insertBSTRecursiveHelper(Node<Integer> root, int value) {
//		return null;
//	}
	
	// O(nlgn)
	public static Node<Integer> insertBSTIterativeHelper(Node<Integer> root, int value) {
		if (root == null)
			return new Node<Integer>(value);
		
		Node<Integer> node = root;
		while (node != null) {
			if (value < node.value) {
				if (node.left != null) {
					node = node.left;
				}
				else {
					node.left = new Node<Integer>(value);
					node = null;
				}
			} 
			else if (value >= node.value) {
				if (node.right != null) {
					node = node.right;
				}
				else {
					node.right = new Node<Integer>(value);
					node = null;
				}
			}
		}
		return root;
	}
	
	/**
	 * 
	 */
	public ReconstructBST() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<Integer> list = new LinkedList<Integer>();
		// pre-order	30 20 10 40 35 50 
		list.add(30);
		list.add(20);
		list.add(10);
		list.add(40);
		list.add(35);
		list.add(50);
		LevelByLevelTraversal.traverseByLevel(readBSTInsert(list));
		LevelByLevelTraversal.traverseByLevel(readBST(list));
	}

}
